package q655_printTree;

import CommonClass.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    /*
    注意题目中求的height和使用maxDepth函数所求出的实际上相差1
    因此部分参数需要调整
    其余的步骤只需要按照题设赋值的过程即可
    也可以不构建matrix数组，直接先建好ArrayList，全部赋值为""
    然后再dfs，可以节约内存
     */
    public List<List<String>> printTree(TreeNode root) {
        int m = maxDepth(root), n = (1 << (m)) - 1;
        int[][] matrix = new int[m][n];
        for (int[] ins : matrix) {
            Arrays.fill(ins, -100);
        }
        dfs(root, 0, (n - 1) / 2, matrix);

        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            List<String> temp = new ArrayList<>();
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == -100) temp.add("");
                else temp.add(String.valueOf(matrix[i][j]));
            }
            res.add(new ArrayList<>(temp));
        }
        return res;
    }

    private void dfs(TreeNode root, int r, int c, int[][] matrix) {
        matrix[r][c] = root.val;
        if (root.left != null) {
            dfs(root.left, r + 1, c - (1 << (matrix.length - r - 2)), matrix);
        }

        if (root.right != null) {
            dfs(root.right, r + 1, c + (1 << (matrix.length - r - 2)), matrix);
        }
    }

    private int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
}
